package leetcode_300;

import java.util.ArrayList;

import java.util.List;

import helpclass.TreeNode;

/**
 *@author 周杨
 *SerializeAndDeserializeBinaryTree_297 编码一个二叉树 并给出解码方法  这种树是有重复数字的 并不可以用先序和中序编码
 *describe:用dfs遍历一棵树 要保存null节点 也可以用层次遍历  AC 60%
 *2018年6月29日 上午10:48:54
 */
public class SerializeAndDeserializeBinaryTree_297 {
	public static void main(String[] args) {
		SerializeAndDeserializeBinaryTree_297 test=new SerializeAndDeserializeBinaryTree_297();
		TreeNode root=new TreeNode(1);
		root.left=new TreeNode(2);
		root.right=new TreeNode(3);
		root.right.left=new TreeNode(4);
		root.right.right=new TreeNode(5);
		System.out.println(test.serialize(root));

	}
	 // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
    	List<String> list = new ArrayList<String>();
        serialize(root, list);
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<list.size(); i++) {
            sb.append(list.get(i)+",");
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
    	if(data == null || data.length() == 0) return null;
        return deserialize(data.split(","), new int[1]);
    }
    
    public void serialize(TreeNode root, List<String> list) {
        if(root == null) {
            list.add("null");
            return;
        }
        list.add(String.valueOf(root.val));
        serialize(root.left, list);
        serialize(root.right, list);
    }
    
    public TreeNode deserialize(String[] data, int[] index) {
        if(index[0]>=data.length || data[index[0]].equals("null")) {
            index[0]++;
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(data[index[0]++]));
        root.left = deserialize(data, index);
        root.right = deserialize(data, index);
        return root;
    }
    
    
	
}
